1. Field of Invention
The invention relates generally to the field of allocating memory in a computer system and, more specifically, to a technique for improving the efficiency of a garbage collector.
2. Description of Related Art
Memory resources in computer systems are allocated for storing abstract data objects or items. When the objects are no longer needed, it is necessary to re-allocate the associated memory resources. To this end, garbage collectors, which are part of the run-time system, have been developed to provide automatic periodic storage reclamation of dynamically allocated memory resources. Automatic garbage collection is usually triggered during memory allocation when the amount of free memory falls below some threshold or after a certain number of allocations. Normal execution is suspended and the garbage collector is run. Garbage collection occurs in two phases: identifying unneeded objects, and making their storage available for reallocation. An object in a program is needed, or live, at a given time if the program might access that object in the future. Otherwise, the object is dead. This may occur if the program has abandoned all pointers to it, making future access impossible.
There are two principle approaches to garbage collection. Reference counting garbage collectors maintain a count for each object of the number of pointers to it. An object is therefore dead when its count falls to zero. Tracing collectors identify as live those objects that are accessible either directly or indirectly from a set of root cells, which are typically the registers and named variables of the program. Objects that are not encountered during the trace are considered to be dead. Tracing collectors include copying collectors, which relocate live objects into a new memory area as they encountered during the trace, and marking collectors, which flag live objects during the trace.
Tracing collectors have been much more commonly used due to perceived deficiencies in reference counting. In particular, a problem with reference counting garbage collectors is that they normally cannot detect garbage that has loops, e.g., cyclic data structures, in it. For example, if there is an object “A” that points to an object “B”, and “B” points back to “A”, then both objects will have non-zero reference counts even when no outside data ever references them. They might be garbage because they are inaccessible, but the algorithm will not recognize that. Thus, any reference counting garbage collector must periodically search for objects that have a non-zero reference count but are inaccessible. This is expensive in terms of time and processing resources, e.g., processor cycles.